package algotithm.weekendrace.leetcode225.test2;

/**
 * @author zhouyanxiang
 * @Date 2021-01-2021/1/24-10:09
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        String a = "dabadd";
        String b = "cda";
        int minCharacters = solution.minCharacters(a, b);
        System.out.println(minCharacters);
    }

    public int minCharacters(String a, String b) {
        int[] countA = new int[26], countB = new int[26];
        for (char c : a.toCharArray()) {
            countA[c - 'a'] += 1;
        }
        for (char c : b.toCharArray()) {
            countB[c - 'a'] += 1;
        }
        int res = Integer.MAX_VALUE;
        res = Math.min(res, lessThan(countA, countB));
        res = Math.min(res, lessThan(countB, countA));
        res = Math.min(res, distinct(countA, a.length()) + distinct(countB, b.length()));
        return res;
    }

    private int lessThan(int[] c1, int[] c2) {
        int sum = 0;
        for (int i : c1) {
            sum += i;
        }
        int min = Integer.MAX_VALUE;
        int sumRight = 0;
        for (int i = 0; i < 25; ++i) {
            sumRight += c2[i];
            sum -= c1[i];
            min = Math.min(min, sum + sumRight);
        }
        return min;
    }

    private int distinct(int[] c1, int len) {
        int min = Integer.MAX_VALUE;
        for (int i : c1) {
            min = Math.min(min, len - i);
        }
        return min;
    }
}


